993. 二叉树的堂兄弟节点

// 在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。
// 如果二叉树的两个节点深度相同，但 父节点不同 ，则它们是一对堂兄弟节点。
// 我们给出了具有唯一值的二叉树的根节点 root ，以及树中两个不同节点的值 x 和 y 。
// 只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true 。否则，返回 false。
var isCousins = function(root, x, y) {
  // 边界处理
  if (!root.left && !root.right) return false;
  // 存储匹配到x和y结果的存储的数据,包括层级depth和父集parent
  let leftDepth = {},
    rightDepth = {};

  getDepth(root.left, { depth: 0, parent: root });
  getDepth(root.right, { depth: 0, parent: root });

  // 递归判断val值和x,y是否相等确定层级和父集
  function getDepth(params, config) {
    if (!params) return;
    if (params.val === x) {
      leftDepth = config;
    } else if (params.val === y) {
      rightDepth = config;
    } else {
      getDepth(params.left, { depth: config.depth + 1, parent: params });
      getDepth(params.right, { depth: config.depth + 1, parent: params });
    }
  }

  return (
    leftDepth.depth > 0 &&
    leftDepth.depth === rightDepth.depth &&
    leftDepth.parent.val !== rightDepth.parent.val
  );
};

const root = { val: 1, left: { val: 2, left: { val: 4 } }, right: { val: 3 } },
  x = 4,
  y = 3;
const root1 = {
    val: 1,
    left: {
      val: 2,
      right: { val: 4 },
    },
    right: {
      val: 3,
      right: { val: 5 },
    },
  },
  x1 = 5,
  y1 = 4;

const root2 = {
    val: 1,
    left: { val: 2, right: { val: 4 } },
    right: { val: 3 },
  },
  x2 = 2,
  y2 = 3;

const root3 = {
    val: 1,
    left: { val: 2 },
    right: { val: 3, left: { val: 4 }, right: { val: 5 } },
  },
  x3 = 4,
  y3 = 5;

console.log(isCousins(root, x, y)); // false
console.log(isCousins(root1, x1, y1)); // true
console.log(isCousins(root2, x2, y2)); // false
console.log(isCousins(root3, x3, y3)); // false